package com.zzg.algorithm.dijkstra.entity;

import java.util.Arrays;

/**
 * @Author zhengzg
 * @Date 2022-10-10
 * @Version v1.0
 */
public class Graph {
    /**
     * 顶点数组
     */
    private char[] vertex;

    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 已经访问顶点的集合
     */
    private VisitedVertex vv;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    // 显示结果
    public void show() {
        vv.show();
    }

    // 显示图
    public void showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    // 迪杰斯特拉算法
    public void dsji(int index) {
        vv = new VisitedVertex(vertex.length, index);
        // 更新index顶点到周围顶点的距离和前驱顶点
        update(index);
        for (int j = 0; j < vertex.length; j++) {
            // 选择并放回新的访问顶点
            index = vv.updateArr();
            // 更新index顶点到周围顶点的距离和前驱结点
            update(index);
        }
    }

    /**
     * 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
     *
     * @param index
     */
    private void update(int index) {
        int len = 0;
        // 根据遍历我们的邻接矩阵行
        for (int j = 0; j < matrix[index].length; j++) {
            // len含义：出发顶点到index顶点的巨鹿 + 从index到j顶点的距离的和
            len = vv.getDis(index) + matrix[index][j];
            // 如果j没有访问过，并且len小于出发顶点到j顶点的距离就需要更新
            if (!vv.in(j) && len < vv.getDis(j)) {
                // 更新j顶点的前驱为index顶点
                vv.updatePre(j, index);
                //更新出发顶点到j顶点的距离
                vv.updateDis(j, len);
            }
        }

    }
}
